﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinaryTree
{
    /// <summary>
    /// 后序遍历
    /// </summary>
    class LastOrder
    {
        /// <summary>
        /// 递归
        /// </summary>
        /// <param name="tree"></param>
        public static void PostOrder(CreatTree.Tree tree)
        {
            if (tree == null) return;
            PostOrder(tree.Left);
            PostOrder(tree.Right);
            Console.Write(tree.Value);
        }
        /// <summary>
        /// 非递归1
        /// </summary>
        /// <param name="tree"></param>
        public static void PostOrderNoRecursion(CreatTree.Tree tree)
        {
            if (tree == null) return;
            Stack<CreatTree.Tree> stack = new Stack<CreatTree.Tree>();
            CreatTree.Tree node = tree;
            CreatTree.Tree pre = null;
            stack.Push(node);
            while (stack.Any())
            {
                node = stack.Peek();
                if ((node.Left == null&&node.Right == null)||(pre!=null&&(pre==node.Left||pre==node.Right)))
                {
                    Console.WriteLine(node.Value);
                    pre = node;
                    stack.Pop();
                }
                else
                {
                    if (node.Right!=null)
                    {
                        stack.Push(node.Right);
                    }
                    if (node.Left!=null)
                    {
                        stack.Push(node.Left);
                    }
                }
            }
        }
        /// <summary>
        /// 非递归2
        /// </summary>
        /// <param name="tree"></param>
        public static void PostOrderNoRecursion2(CreatTree.Tree tree)
        {
            HashSet<CreatTree.Tree> visited = new HashSet<CreatTree.Tree>();
            Stack<CreatTree.Tree> stack = new Stack<CreatTree.Tree>();
            CreatTree.Tree node = tree;

            while (node!=null||stack.Any())
            {
                if (node!=null)
                {
                    stack.Push(node);
                    node = node.Left;
                }
                else
                {
                    var item = stack.Peek();
                    if (item.Right != null && !visited.Contains(item.Right))
                    {
                        node = item.Right;
                    }
                    else
                    {
                        Console.WriteLine(item.Value);
                        visited.Add(item);
                        stack.Pop();
                    }
                }
            }
        }
    }
}
